{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Lexicographically Smallest Equivalent String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #union-find #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #并查集 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: smallestEquivalentString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #按字典序排列最小的等效字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给出长度相同的两个字符串<code>s1</code> 和&nbsp;<code>s2</code>&nbsp;，还有一个字符串&nbsp;<code>baseStr</code>&nbsp;。</p>\n",
    "\n",
    "<p>其中 &nbsp;<code>s1[i]</code>&nbsp;和&nbsp;<code>s2[i]</code>&nbsp; 是一组等价字符。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>举个例子，如果&nbsp;<code>s1 = \"abc\"</code> 且&nbsp;<code>s2 = \"cde\"</code>，那么就有&nbsp;<code>'a' == 'c', 'b' == 'd', 'c' == 'e'</code>。</li>\n",
    "</ul>\n",
    "\n",
    "<p>等价字符遵循任何等价关系的一般规则：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><strong>&nbsp;自反性&nbsp;</strong>：<code>'a' == 'a'</code></li>\n",
    "\t<li>&nbsp;<strong>对称性&nbsp;</strong>：<code>'a' == 'b'</code> 则必定有 <code>'b' == 'a'</code></li>\n",
    "\t<li>&nbsp;<strong>传递性</strong> ：<code>'a' == 'b'</code> 且 <code>'b' == 'c'</code> 就表明 <code>'a' == 'c'</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>例如，&nbsp;<code>s1 = \"abc\"</code>&nbsp;和&nbsp;<code>s2 = \"cde\"</code>&nbsp;的等价信息和之前的例子一样，那么&nbsp;<code>baseStr = \"eed\"</code>&nbsp;, <code>\"acd\"</code>&nbsp;或&nbsp;<code>\"aab\"</code>，这三个字符串都是等价的，而&nbsp;<code>\"aab\"</code>&nbsp;是&nbsp;<code>baseStr</code>&nbsp;的按字典序最小的等价字符串</p>\n",
    "\n",
    "<p>利用<em>&nbsp;</em><code>s1</code>&nbsp;和&nbsp;<code>s2</code>&nbsp;的等价信息，找出并返回<em>&nbsp;</em><code>baseStr</code><em>&nbsp;</em>的按字典序排列最小的等价字符串。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s1 = \"parker\", s2 = \"morris\", baseStr = \"parser\"\n",
    "<strong>输出：</strong>\"makkek\"\n",
    "<strong>解释：</strong>根据 <code>A</code> 和 <code>B 中的等价信息，</code>我们可以将这些字符分为 <code>[m,p]</code>, <code>[a,o]</code>, <code>[k,r,s]</code>, <code>[e,i] 共 4 组</code>。每组中的字符都是等价的，并按字典序排列。所以答案是 <code>\"makkek\"</code>。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s1 = \"hello\", s2 = \"world\", baseStr = \"hold\"\n",
    "<strong>输出：</strong>\"hdld\"\n",
    "<strong>解释：</strong>根据 <code>A</code> 和 <code>B 中的等价信息，</code>我们可以将这些字符分为 <code>[h,w]</code>, <code>[d,e,o]</code>, <code>[l,r] 共 3 组</code>。所以只有 S 中的第二个字符 <code>'o'</code> 变成 <code>'d'，最后答案为 </code><code>\"hdld\"</code>。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s1 = \"leetcode\", s2 = \"programs\", baseStr = \"sourcecode\"\n",
    "<strong>输出：</strong>\"aauaaaaada\"\n",
    "<strong>解释：</strong>我们可以把 A 和 B 中的等价字符分为 <code>[a,o,e,r,s,c]</code>, <code>[l,p]</code>, <code>[g,t]</code> 和 <code>[d,m] 共 4 组</code>，因此 <code>S</code> 中除了 <code>'u'</code> 和 <code>'d'</code> 之外的所有字母都转化成了 <code>'a'</code>，最后答案为 <code>\"aauaaaaada\"</code>。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s1.length, s2.length, baseStr &lt;= 1000</code></li>\n",
    "\t<li><code>s1.length == s2.length</code></li>\n",
    "\t<li>字符串<code>s1</code>,&nbsp;<code>s2</code>, and&nbsp;<code>baseStr</code>&nbsp;仅由从&nbsp;<code>'a'</code> 到&nbsp;<code>'z'</code>&nbsp;的小写英文字母组成。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [lexicographically-smallest-equivalent-string](https://leetcode.cn/problems/lexicographically-smallest-equivalent-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [lexicographically-smallest-equivalent-string](https://leetcode.cn/problems/lexicographically-smallest-equivalent-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"parker\"\\n\"morris\"\\n\"parser\"', '\"hello\"\\n\"world\"\\n\"hold\"', '\"leetcode\"\\n\"programs\"\\n\"sourcecode\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.root = [i for i in range(n)]\n",
    "\n",
    "    def find(self, x):\n",
    "        if x != self.root[x]:\n",
    "            # 在查询的时候合并到顺带直接根节点\n",
    "            root_x = self.find(self.root[x])\n",
    "            self.root[x] = root_x\n",
    "            return root_x\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return\n",
    "        if root_x < root_y:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.root[root_x] = root_y\n",
    "        return\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        n = len(s1)\n",
    "        uf = UnionFind(26)\n",
    "        for i in range(n):\n",
    "            uf.union(ord(s1[i]) - ord(\"a\"), ord(s2[i]) - ord(\"a\"))\n",
    "        ans = \"\"\n",
    "        for w in baseStr:\n",
    "            ans += chr(uf.find(ord(w) - ord(\"a\")) + ord(\"a\"))\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        cur = [i for i in range(26)]\n",
    "        for a, b in zip(s1, s2):\n",
    "            ai = ord(a) - 97\n",
    "            bi = ord(b) - 97\n",
    "            mini = min(cur[ai], cur[bi])\n",
    "            maxi = max(cur[ai], cur[bi])\n",
    "            for i in range(26):\n",
    "                if cur[i] == maxi:\n",
    "                    cur[i] = mini\n",
    "        ans = ''\n",
    "        for t in baseStr:\n",
    "            ti = ord(t) - 97\n",
    "            curt = chr(cur[ti] + 97)\n",
    "            ans += curt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        n = len(s1)\n",
    "        uf = UnionFind(26)\n",
    "        for i in range(n):\n",
    "            uf.union(ord(s1[i])-ord(\"a\"),ord(s2[i])-ord(\"a\"))\n",
    "        ans=\"\"\n",
    "        for w in baseStr:\n",
    "            ans += chr(uf.find(ord(w)-ord(\"a\"))+ord(\"a\"))\n",
    "        return ans\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self,n):\n",
    "        self.root = [i for i in range(n)]\n",
    "    \n",
    "    def find(self,x):\n",
    "        if x != self.root[x]:\n",
    "            root_x=self.find(self.root[x])\n",
    "            self.root[x]=root_x\n",
    "            return root_x\n",
    "        return x\n",
    "    \n",
    "    def union(self,x,y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "\n",
    "        if root_x == root_y:\n",
    "            return \n",
    "        if root_x < root_y:\n",
    "            root_x,root_y = root_y,root_x\n",
    "        self.root[root_x]=root_y\n",
    "        return "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        base = ord('a')\n",
    "        roots = []\n",
    "\n",
    "        for i in range(26):\n",
    "            roots.append(i)\n",
    "\n",
    "        def getroot(node):\n",
    "            while roots[node]!=node:\n",
    "                node = roots[node]\n",
    "            return node\n",
    "\n",
    "        for i in range(len(s1)):\n",
    "            c1 = ord(s1[i])-base\n",
    "            c2 = ord(s2[i])-base\n",
    "            r1 = getroot(c1)\n",
    "            r2 = getroot(c2)\n",
    "            if r1!=r2:\n",
    "                if r1<r2:\n",
    "                    roots[r2]=r1\n",
    "                else:\n",
    "                    roots[r1] = r2\n",
    "        \n",
    "        ret = \"\"\n",
    "        for c in baseStr:\n",
    "            ret += chr(base+getroot(ord(c)-base))\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "\tdef smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\r\n",
    "\t\t# Alternatives\r\n",
    "\t\talter = [] # [set()]\r\n",
    "\r\n",
    "\t\tp = -1\r\n",
    "\t\twhile (p := p + 1) < len(s1):\r\n",
    "\t\t\t# Combine intersected\r\n",
    "\t\t\tmerged = {s1[p], s2[p]}\r\n",
    "\t\t\tmerged_idx = set()\r\n",
    "\t\t\tfor i in range(len(alter)):\r\n",
    "\t\t\t\t# if intersected\r\n",
    "\t\t\t\tif not alter[i].isdisjoint(merged):\r\n",
    "\t\t\t\t\t# merge and pop\r\n",
    "\t\t\t\t\tmerged.update(alter[i])\r\n",
    "\t\t\t\t\tmerged_idx.add(i)\r\n",
    "\t\t\t# remove duplicated and append `merged`\r\n",
    "\t\t\talter = [alter[i] for i in range(len(alter)) if i not in merged_idx] + [merged]\r\n",
    "\r\n",
    "\t\tres = str()\r\n",
    "\t\tfor i in range(len(baseStr)):\r\n",
    "\t\t\tfor collection in alter:\r\n",
    "\t\t\t\tif baseStr[i] in collection:\r\n",
    "\t\t\t\t\tres += min(collection)\r\n",
    "\t\t\t\t\tbreak\r\n",
    "\t\t\telse:\r\n",
    "\t\t\t\tres += baseStr[i]\r\n",
    "\t\treturn res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        data_dict = defaultdict(set)\n",
    "        for i in range(26):\n",
    "            data_dict[chr(ord('a') + i)].add(chr(ord('a') + i))\n",
    "        for i in range(len(s1)):\n",
    "            data_dict[s1[i]].add(s2[i])\n",
    "            data_dict[s2[i]].add(s1[i])\n",
    "        res = ''\n",
    "        \n",
    "        def dfs(ele, res_char, visit, data_dict):\n",
    "            res_char = min(res_char, ele)\n",
    "            if ele not in visit:\n",
    "                visit.add(ele)\n",
    "                for one in data_dict[ele]:\n",
    "                    res_char = min(res_char, dfs(one, res_char, visit, data_dict))\n",
    "            return res_char\n",
    "   \n",
    "        for ele in baseStr:\n",
    "            visit = set()\n",
    "            res += dfs(ele, ele, visit, data_dict)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        u = UnionFind()\n",
    "        n = len(s1)\n",
    "        for i in range(n):\n",
    "            t1 = ord(s1[i]) - 97\n",
    "            t2 = ord(s2[i]) - 97\n",
    "            u.union(t1, t2)\n",
    "        res = \"\"\n",
    "        for c in baseStr:\n",
    "            res += chr(u.find(ord(c)-97) + 97)\n",
    "        return res\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.nodes = [i for i in range(26)]\n",
    "\n",
    "    def find(self, x):\n",
    "        return x if x == self.nodes[x] else self.find(self.nodes[x])\n",
    "\n",
    "    def union(self, x, y):\n",
    "        x = self.find(x)\n",
    "        y = self.find(y)\n",
    "        if x == y:\n",
    "            return\n",
    "        if x < y:\n",
    "            self.nodes[y] = x\n",
    "        else:\n",
    "            self.nodes[x] = y\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self,n):\n",
    "        self.parent = list(range(n))\n",
    "    def find(self,x):\n",
    "        while x != self.parent[x]:\n",
    "            x = self.parent[self.parent[x]]\n",
    "        return self.parent[x]\n",
    "    def union(self,x,y):\n",
    "        p,q = self.find(x),self.find(y)\n",
    "        if p<q:\n",
    "            self.parent[q] = p\n",
    "        elif p>q:\n",
    "            self.parent[p] = q\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        uf = UF(26)\n",
    "        for i in range(len(s1)):\n",
    "            uf.union(ord(s1[i])-ord('a'),ord(s2[i])-ord('a'))\n",
    "        res = \"\"\n",
    "        for i in range(len(baseStr)):\n",
    "            res+=chr(uf.find(ord(baseStr[i])-ord('a'))+ord('a'))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.root = [i for i in range(n)]\n",
    "\n",
    "    def find(self, x):\n",
    "        if x != self.root[x]:\n",
    "            # 在查询的时候合并到顺带直接根节点\n",
    "            root_x = self.find(self.root[x])\n",
    "            self.root[x] = root_x\n",
    "            return root_x\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return\n",
    "        if root_x < root_y:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.root[root_x] = root_y\n",
    "        return\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        n = len(s1)\n",
    "        uf = UnionFind(26)\n",
    "        for i in range(n):\n",
    "            uf.union(ord(s1[i])-ord(\"a\"),ord(s2[i]) - ord(\"a\"))\n",
    "        ans = \"\"\n",
    "        for w in baseStr:\n",
    "            ans +=chr(uf.find(ord(w) - ord(\"a\")) + ord(\"a\"))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        root = [0] * 26\n",
    "        for i in range(26):\n",
    "            root[i] = i\n",
    "        def Find(x) -> int:\n",
    "            if x != root[x]:\n",
    "                root[x] = Find(root[x])\n",
    "            return root[x]\n",
    "        def Union(x,y):\n",
    "            root1 = Find(x)\n",
    "            root2 = Find(y)\n",
    "            if root1 < root2:\n",
    "                root[root2] = root1\n",
    "            else:\n",
    "                root[root1] = root2\n",
    "        def isConnect(x,y) -> bool:\n",
    "            return Find(x) == Find(y)\n",
    "  \n",
    "        m = len(s1)\n",
    "        for i in range(m):\n",
    "            x = ord(s1[i]) - ord('a')\n",
    "            y = ord(s2[i]) - ord('a')\n",
    "            Union(x,y)\n",
    "        n = len(baseStr)\n",
    "        ans = \"\"\n",
    "        for i in range(n):\n",
    "            x = ord(baseStr[i]) - ord('a')\n",
    "            rt = Find(x)\n",
    "            ans += chr(ord('a') + rt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        fa={}\n",
    "        for i in range(26):\n",
    "            ch=chr(ord(\"a\")+i)\n",
    "            fa[ch]=ch\n",
    "        def find(x):\n",
    "            if fa[x]!=x:\n",
    "                fa[x]=find(fa[x])\n",
    "            return fa[x]\n",
    "\n",
    "        def union(a,b):\n",
    "            x,y=find(a),find(b)\n",
    "            if x!=y:\n",
    "                if x<y:\n",
    "                    fa[y]=x\n",
    "                else:\n",
    "                    fa[x]=y\n",
    "        \n",
    "        n=len(s1)\n",
    "        for i in range(n):\n",
    "            union(s1[i],s2[i])\n",
    "        ans=[]\n",
    "        for ch in baseStr:\n",
    "            ans.append(find(ch))\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class unionfind:\n",
    "    def __init__(self, n):\n",
    "        self.root = [i for i in range(n)]\n",
    "            \n",
    "    def find(self, x):\n",
    "        if x != self.root[x]:\n",
    "            root_x = self.find(self.root[x])\n",
    "            self.root[x] = root_x\n",
    "            return root_x\n",
    "        return x \n",
    "            \n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return\n",
    "        if root_x > root_y:\n",
    "            self.root[root_x] = root_y\n",
    "        else:\n",
    "            self.root[root_y] = root_x\n",
    "        return\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        n = len(s1)\n",
    "        uf = unionfind(26)\n",
    "        for i in range(n):\n",
    "            uf.union(ord(s1[i])- ord('a'), ord(s2[i])- ord('a'))\n",
    "        ans = ''\n",
    "        for i in baseStr:\n",
    "            ans += chr(uf.find(ord(i) - ord('a')) + ord('a'))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getIndex(self,w):\n",
    "        return ord(w)-ord('a')\n",
    "    def getRoot(self,equals,i):\n",
    "        while equals[i]!=i:\n",
    "            i= equals[i]\n",
    "        return i\n",
    "    def getChar(self,i):\n",
    "        return chr(ord('a')+i)\n",
    "\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        equals =  [i for i in range(26)]\n",
    "        for i in range(len(s1)):\n",
    "            root_1 = self.getRoot(equals, self.getIndex(s1[i]) )\n",
    "            root_2 = self.getRoot(equals, self.getIndex(s2[i]) )\n",
    "\n",
    "            if root_1<=root_2:\n",
    "                equals[root_2] = root_1\n",
    "            else:\n",
    "                equals[root_1] = root_2\n",
    "        res = \"\"\n",
    "        for i in range(len(baseStr)):\n",
    "            root = self.getRoot(equals,self.getIndex(baseStr[i]))\n",
    "            ch = self.getChar(root)\n",
    "            #print(ch)\n",
    "            res = res+ch\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        # ans = []\n",
    "        # for i in range(len(s1)):\n",
    "        #     ans.append([s1[i,s2[i]]])\n",
    "\n",
    "\n",
    "        #copy\n",
    "        def dfs(ele,res,vis,dic):\n",
    "            res = min(res,ele)\n",
    "            if ele not in vis:\n",
    "                vis.add(ele)\n",
    "                for one in dic[ele]:\n",
    "                    res = min(res,dfs(one,res,vis,dic))\n",
    "\n",
    "            return res\n",
    "        \n",
    "        dic = defaultdict(set)\n",
    "        for i in range(len(s1)):\n",
    "            dic[s1[i]].add(s2[i])\n",
    "            dic[s2[i]].add(s1[i])\n",
    "        res = ''\n",
    "        for ele in baseStr:\n",
    "            vis = set()\n",
    "            res += dfs(ele,ele,vis,dic)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "    \n",
    "\n",
    "\n",
    "        union = Union(26)\n",
    "        for i in range(len(s1)):\n",
    "            union.merge(ord(s1[i]) - ord('a'), ord(s2[i]) - ord('a'))\n",
    "        ans = ''\n",
    "        for e in baseStr:\n",
    "            ans += chr(union.find_parent(ord(e) - ord('a')) + ord('a'))\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Union:\n",
    "        def __init__(self, length: int):\n",
    "            self.nums = [i for i in range(length)]\n",
    "\n",
    "        def find_parent(self, i: int) -> int:\n",
    "            while self.nums[i] != i:\n",
    "                return self.find_parent(self.nums[i])\n",
    "            return self.nums[i]\n",
    "\n",
    "        def merge(self, i: int, j: int):\n",
    "            p_i = self.find_parent(i)\n",
    "            p_j = self.find_parent(j)\n",
    "            self.nums[max(p_j, p_i)] = min(p_j, p_i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        parent_list = [index for index in range(26)]\n",
    "        answer_list = list(baseStr)\n",
    "        for letter1, letter2 in zip(s1, s2):\n",
    "            parent_letter1 = find(parent_list, ord(letter1) - ord('a'))\n",
    "            parent_letter2 = find(parent_list, ord(letter2) - ord('a'))\n",
    "            if parent_letter1 < parent_letter2:\n",
    "                union(parent_list, parent_letter2, parent_letter1)\n",
    "            elif parent_letter1 > parent_letter2:\n",
    "                union(parent_list, parent_letter1, parent_letter2)\n",
    "        for index in range(len(baseStr)):\n",
    "            answer_list[index] = chr(find(parent_list, ord(baseStr[index]) - ord('a')) + ord('a'))\n",
    "        return ''.join(answer_list)\n",
    "\n",
    "def find(parent_list, index):\n",
    "    if parent_list[index] != index:\n",
    "        parent_list[index] = find(parent_list, parent_list[index])\n",
    "    return parent_list[index]\n",
    "\n",
    "def union(parent_list, index1, index2):\n",
    "    parent_list[find(parent_list, index1)] = find(parent_list, index2)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        data_dict = defaultdict(set)\n",
    "        for i in range(len(s1)):\n",
    "            data_dict[s1[i]].add(s2[i])\n",
    "            data_dict[s2[i]].add(s1[i])\n",
    "        res = ''\n",
    "        \n",
    "        def dfs(ele):\n",
    "            ans = ele\n",
    "            temp = [ele]\n",
    "            visit = [False for _ in range(26)]\n",
    "            visit[ord(ele) - ord('a')] = True\n",
    "            while temp:\n",
    "                a = temp.pop()\n",
    "                ans = min(a, ans)\n",
    "                for point in data_dict[a]:\n",
    "                    if visit[ord(point) - ord('a')] == False:\n",
    "                        temp.append(point)\n",
    "                        visit[ord(point) - ord('a')] = True\n",
    "            return ans\n",
    "   \n",
    "        for ele in baseStr:\n",
    "            res += dfs(ele)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        parents = [i for i in range(26)]\n",
    "        def find(x):\n",
    "            return x if parents[x] == x else find(parents[x])\n",
    "        \n",
    "        def is_connect(x, y):\n",
    "            return find(x) == find(y)\n",
    "\n",
    "        def union(x, y):\n",
    "            if is_connect(x, y): return\n",
    "            px = find(x)\n",
    "            py = find(y)\n",
    "            parents[max(px, py)] = min(px, py)\n",
    "\n",
    "        for c1, c2 in zip(s1, s2):\n",
    "            i1 = ord(c1) - ord('a')\n",
    "            i2 = ord(c2) - ord('a')\n",
    "            union(i1, i2)\n",
    "        \n",
    "        res = []\n",
    "        for c in baseStr:\n",
    "            i = ord(c) - ord('a')\n",
    "            res.append(chr(find(i) + ord('a')))\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.root = [i for i in range(26)]\n",
    "        \n",
    "    def union(self,x,y):\n",
    "        while self.root[x]!=x:\n",
    "            x = self.root[x]\n",
    "        while self.root[y] !=y:\n",
    "            y = self.root[y]\n",
    "        if x == y:\n",
    "            return\n",
    "        if x < y:\n",
    "            x,y = y,x\n",
    "        self.root[x] = y\n",
    "        \n",
    "    def find(self,x):\n",
    "        while self.root[x] != x:\n",
    "            x = self.root[x]\n",
    "        return x\n",
    "        \n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        for c1,c2 in zip(s1,s2):\n",
    "            self.union(ord(c1)-ord('a'),ord(c2)-ord('a'))\n",
    "        res = ''\n",
    "        for i,c in enumerate(baseStr):\n",
    "            #print(i,c)\n",
    "            res += chr(self.find(ord(c)-ord('a')) + ord('a'))\n",
    "        return res\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "\tdef smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\r\n",
    "\t\t# Alternatives\r\n",
    "\t\talter = [] # [set()]\r\n",
    "\t\tp = -1\r\n",
    "\t\twhile (p := p + 1) < len(s1):\r\n",
    "\t\t\t# Combine intersected\r\n",
    "\t\t\tmerged = {s1[p], s2[p]}\r\n",
    "\t\t\tmerged_idx = set()\r\n",
    "\t\t\tfor i in range(len(alter)):\r\n",
    "\t\t\t\t# if intersected\r\n",
    "\t\t\t\tif not alter[i].isdisjoint(merged):\r\n",
    "\t\t\t\t\t# merge and pop\r\n",
    "\t\t\t\t\tmerged.update(alter[i])\r\n",
    "\t\t\t\t\tmerged_idx.add(i)\r\n",
    "\t\t\t# remove duplicated and append `merged`\r\n",
    "\t\t\talter = [alter[i] for i in range(len(alter)) if i not in merged_idx] + [merged]\r\n",
    "\r\n",
    "\t\t# Link char with smallest equivalent in DICT\r\n",
    "\t\tequiv = {}\r\n",
    "\t\tfor s in alter:\r\n",
    "\t\t\tmin_eq = min(s)\r\n",
    "\t\t\tfor c in s:\r\n",
    "\t\t\t\tequiv[c] = min_eq\r\n",
    "\r\n",
    "\t\tres = str()\r\n",
    "\t\tfor c in baseStr:\r\n",
    "\t\t\tres += equiv.get(c, c)\r\n",
    "\r\n",
    "\t\treturn res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        def find_ancestor(x):\n",
    "            if x not in equal:\n",
    "                equal[x] = x\n",
    "            if equal[x] != x:\n",
    "                equal[x] = find_ancestor(equal[x])\n",
    "            return equal[x]\n",
    "        \n",
    "        def union(x, y):\n",
    "            ancestor_x, ancestor_y = find_ancestor(x), find_ancestor(y)\n",
    "            min_val = min(ancestor_x, ancestor_y)\n",
    "            equal[ancestor_x] = equal[ancestor_y] = min_val\n",
    "        \n",
    "        equal = {}\n",
    "        for x, y in zip(s1, s2):\n",
    "            union(x, y)\n",
    "        return ''.join(find_ancestor(x) for x in baseStr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        parent_list = [index for index in range(26)]\n",
    "        answer_list = list(baseStr)\n",
    "        for letter1, letter2 in zip(s1, s2):\n",
    "            parent_letter1 = find(parent_list, ord(letter1) - ord('a'))\n",
    "            parent_letter2 = find(parent_list, ord(letter2) - ord('a'))\n",
    "            if parent_letter1 < parent_letter2:\n",
    "                union(parent_list, parent_letter2, parent_letter1)\n",
    "            elif parent_letter1 > parent_letter2:\n",
    "                union(parent_list, parent_letter1, parent_letter2)\n",
    "        for index in range(len(baseStr)):\n",
    "            answer_list[index] = chr(find(parent_list, ord(baseStr[index]) - ord('a')) + ord('a'))\n",
    "        return ''.join(answer_list)\n",
    "\n",
    "def find(parent_list, index):\n",
    "    if parent_list[index] != index:\n",
    "        parent_list[index] = find(parent_list, parent_list[index])\n",
    "    return parent_list[index]\n",
    "\n",
    "def union(parent_list, index1, index2):\n",
    "    parent_list[index1] = index2\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        n = len(s1)\n",
    "\n",
    "        f = [i for i in range(27)]\n",
    "        def find(x):\n",
    "            if f[x] != x:\n",
    "                f[x] = find(f[x])\n",
    "            return f[x]\n",
    "\n",
    "        for i in range(n):\n",
    "            if s1[i] != s2[i]:\n",
    "                a, b = ord(s1[i]) - ord('a'), ord(s2[i]) - ord('a')\n",
    "                tx = find(a)\n",
    "                ty = find(b)\n",
    "                if tx != ty:\n",
    "                    if tx < ty: \n",
    "                        f[ty] = tx\n",
    "                    else:\n",
    "                        f[tx] = ty\n",
    "        ans = \"\"\n",
    "        for ba in baseStr:\n",
    "            t = ord(ba) - ord('a')\n",
    "            tt = find(t)\n",
    "            ans += chr(ord('a') + tt)\n",
    "\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        def dfs(ele, res_char, visit, data_dict):\n",
    "            res_char = min(res_char, ele)\n",
    "            if ele not in visit:\n",
    "                visit.add(ele)\n",
    "                for one in data_dict[ele]:\n",
    "                    res_char = min(res_char, dfs(one, res_char, visit, data_dict))\n",
    "            return res_char\n",
    "        data_dict = collections.defaultdict(set)\n",
    "        for i in range(len(s1)):\n",
    "            data_dict[s1[i]].add(s2[i])\n",
    "            data_dict[s2[i]].add(s1[i])\n",
    "        res = \"\"\n",
    "        for ele in baseStr:\n",
    "            visit = set()\n",
    "            res += dfs(ele, ele, visit, data_dict)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        parent_list = [index for index in range(26)]\n",
    "        answer_list = list(baseStr)\n",
    "        for letter1, letter2 in zip(s1, s2):\n",
    "            if find(parent_list, ord(letter1) - ord('a')) < find(parent_list, ord(letter2) - ord('a')):\n",
    "                union(parent_list, ord(letter2) - ord('a'), ord(letter1) - ord('a'))\n",
    "            elif find(parent_list, ord(letter1) - ord('a')) > find(parent_list, ord(letter2) - ord('a')):\n",
    "                union(parent_list, ord(letter1) - ord('a'), ord(letter2) - ord('a'))\n",
    "        for index in range(len(baseStr)):\n",
    "            answer_list[index] = chr(find(parent_list, ord(baseStr[index]) - ord('a')) + ord('a'))\n",
    "        return ''.join(answer_list)\n",
    "\n",
    "def find(parent_list, index):\n",
    "    if parent_list[index] != index:\n",
    "        parent_list[index] = find(parent_list, parent_list[index])\n",
    "    return parent_list[index]\n",
    "\n",
    "def union(parent_list, index1, index2):\n",
    "    parent_list[find(parent_list, index1)] = find(parent_list, index2)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.parents = [i for i in range(n)]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x, root_y = self.find(x),  self.find(y)\n",
    "        if root_x != root_y:\n",
    "            if root_x > root_y:\n",
    "                self.parents[root_x] = root_y\n",
    "            else:\n",
    "                self.parents[root_y] = root_x\n",
    "\n",
    "    def find(self, x):\n",
    "        if x== self.parents[x]:\n",
    "            return x\n",
    "        self.parents[x] = self.find(self.parents[x])\n",
    "        return self.parents[x]\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        uni = UnionFind(26)\n",
    "        for i in range(len(s1)):\n",
    "            uni.union(ord(s1[i])-ord('a'), ord(s2[i])-ord('a'))\n",
    "        ans = [chr(uni.find(ord(c)-ord('a'))+ord('a')) for c in baseStr]\n",
    "        return \"\".join(ans)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "            for i in range(len(s1)):\n",
    "                if ord(s1[i])<ord(s2[i]):\n",
    "                    a = s1[i]\n",
    "                    b = s2[i]\n",
    "                else:\n",
    "                    a = s2[i]\n",
    "                    b = s1[i]\n",
    "                s1 = s1.replace(b,a)\n",
    "                s2 = s2.replace(b,a)\n",
    "                baseStr = baseStr.replace(b,a)\n",
    "            return baseStr\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        parent_list = [index for index in range(26)]\n",
    "        answer_list = list(baseStr)\n",
    "        for letter1, letter2 in zip(s1, s2):\n",
    "            if find(parent_list, ord(letter1) - ord('a')) < find(parent_list, ord(letter2) - ord('a')):\n",
    "                union(parent_list, ord(letter2) - ord('a'), ord(letter1) - ord('a'))\n",
    "            elif find(parent_list, ord(letter1) - ord('a')) > find(parent_list, ord(letter2) - ord('a')):\n",
    "                union(parent_list, ord(letter1) - ord('a'), ord(letter2) - ord('a'))\n",
    "        for index in range(len(baseStr)):\n",
    "            answer_list[index] = chr(find(parent_list, ord(baseStr[index]) - ord('a')) + ord('a'))\n",
    "        return ''.join(answer_list)\n",
    "\n",
    "def find(parent_list, index):\n",
    "    if parent_list[index] != index:\n",
    "        parent_list[index] = find(parent_list, parent_list[index])\n",
    "    return parent_list[index]\n",
    "\n",
    "def union(parent_list, index1, index2):\n",
    "    parent_list[find(parent_list, index1)] = find(parent_list, index2)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionSet:\n",
    "    def __init__(self):\n",
    "        self.parents = {}\n",
    "    def find(self, x):\n",
    "        if(x != self.parents[x]):\n",
    "            self.parents[x] = self.find(self.parents[x])\n",
    "        return self.parents[x]\n",
    "    def union(self, x, y):\n",
    "        ax = self.find(x)\n",
    "        ay = self.find(y)\n",
    "        if(ax == ay):\n",
    "            return True\n",
    "        if(ax < ay):\n",
    "            ax, ay = ay, ax \n",
    "        self.parents[ax] = ay \n",
    "        return False\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        us = UnionSet()\n",
    "        for i in range(26):\n",
    "            us.parents[chr(i+ord('a'))] = chr(i+ord('a'))\n",
    "        for c1, c2 in zip(s1, s2):\n",
    "            us.union(c1,c2)\n",
    "        result = ''\n",
    "        for c in baseStr:\n",
    "            result += us.find(c)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self):\n",
    "        self.parent = [i for i in range(26)]\n",
    "        self.rank = [i for i in range(26)]\n",
    "\n",
    "    def find(self, i):\n",
    "        while (i != self.parent[i]):\n",
    "            i, self.parent[i] = self.parent[i], self.parent[self.parent[i]]\n",
    "        return i \n",
    "    \n",
    "    def union(self, i, j):\n",
    "        pi, pj = self.find(i), self.find(j)\n",
    "\n",
    "        # pi: parent with smaller rank\n",
    "        if (self.rank[pi] > self.rank[pj]):\n",
    "            pi, pj = pj, pi \n",
    "        \n",
    "        self.parent[pj] = pi \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        n = len(s1)\n",
    "        uf = UF()\n",
    "\n",
    "        def getOrd(i):\n",
    "            return ord(i) - ord('a')\n",
    "\n",
    "        for i in range(n):\n",
    "            uf.union(getOrd(s1[i]), getOrd(s2[i]))\n",
    "        \n",
    "        mp = {}\n",
    "        for i in range(26):\n",
    "            mp[i] = uf.find(i)\n",
    "\n",
    "        def itoc(i):\n",
    "            return chr(i + ord('a'))\n",
    "\n",
    "        res = \"\"\n",
    "        for i in range(len(baseStr)):\n",
    "            target = mp[getOrd(baseStr[i])]\n",
    "            res += itoc(target)\n",
    "\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Floyd\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        g = [[0] * 26 for _ in range(26)]\n",
    "        n = len(s1)\n",
    "        for i in range(n):\n",
    "            x, y = s1[i], s2[i]\n",
    "            x, y = ord(x) - ord('a'), ord(y) - ord('a')\n",
    "            g[x][y] = g[y][x] = 1\n",
    "        for i in range(26):\n",
    "            g[i][i] = 1\n",
    "        for k in range(26):\n",
    "            for i in range(26):\n",
    "                for j in range(26):\n",
    "                    g[i][j] |= g[i][k] and g[k][j]\n",
    "        ans = ''\n",
    "        for x in baseStr:\n",
    "            x = ord(x) - ord('a')\n",
    "            for i in range(26):\n",
    "                if g[x][i]:\n",
    "                    ans += chr(ord('a') + i)\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, n):\n",
    "        self.p = [i for i in range(n + 1)]\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.p[x] != x:\n",
    "            self.p[x] = self.find(self.p[x])\n",
    "        return self.p[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        px, py = self.find(x), self.find(y)\n",
    "        if px == py:\n",
    "            return\n",
    "        if py < px:\n",
    "            self.p[px] = py\n",
    "        else:\n",
    "            self.p[py] = px\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        dsu = DSU(26)\n",
    "        for c1, c2 in zip(s1, s2):\n",
    "            t1, t2 = ord(c1) - ord('a'), ord(c2) - ord('a')\n",
    "            dsu.union(t1, t2)\n",
    "        ans = \"\"\n",
    "        for c in baseStr:\n",
    "            ans += chr(dsu.find(ord(c) - ord('a')) + ord('a'))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.parent = {}\n",
    "\n",
    "    def find(self, x):\n",
    "        self.parent.setdefault(x, x)\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def union_rank(self, x: int, y: int):\n",
    "        x_root, y_root = self.find(x), self.find(y)\n",
    "        if x_root != y_root:\n",
    "            if y_root > x_root:\n",
    "                self.parent[y_root] = x_root\n",
    "            else:\n",
    "                self.parent[x_root] = y_root\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        uf = UnionFind()\n",
    "        for a, b in zip(s1, s2):\n",
    "            uf.union_rank(a, b)\n",
    "        ret = ''\n",
    "        for c in baseStr:\n",
    "            ret += uf.find(c)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import string\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        p = {c:c for c in string.ascii_lowercase}\n",
    "        def find_root(a):\n",
    "            if p[a] != a:\n",
    "                p[a] = find_root(p[a])\n",
    "            return p[a]\n",
    "\n",
    "        for a, b in zip(s1, s2):\n",
    "            r_a = find_root(a)\n",
    "            r_b = find_root(b)\n",
    "            if ord(r_a) < ord(r_b):\n",
    "                p[r_b] = r_a\n",
    "            else:\n",
    "                p[r_a] = r_b\n",
    "        ans = ''\n",
    "        for c in baseStr:\n",
    "            ans += find_root(c)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        class UnionFind:\n",
    "            def __init__(self, s1, s2):\n",
    "                self.parents = dict()\n",
    "                for i in range(len(s1)):\n",
    "                    self.parents[s1[i]] = s1[i]\n",
    "                    self.parents[s2[i]] = s2[i]\n",
    "            \n",
    "            def find(self, x):\n",
    "                if x not in self.parents.keys():\n",
    "                    return x\n",
    "                while True:\n",
    "                    if self.parents[x]==x:\n",
    "                        return x\n",
    "                    else:\n",
    "                        x = self.parents[x]\n",
    "            \n",
    "            def union(self, a, b):\n",
    "                p_a = self.find(a)\n",
    "                p_b = self.find(b)\n",
    "                if p_a<=p_b:\n",
    "                    self.parents[p_b] = p_a\n",
    "                else:\n",
    "                    self.parents[p_a] = p_b\n",
    "        \n",
    "\n",
    "        uf = UnionFind(s1, s2)\n",
    "        for i in range(len(s1)):\n",
    "            uf.union(s1[i], s2[i])\n",
    "\n",
    "        ans = []\n",
    "        for char in baseStr:\n",
    "            temp = uf.find(char)\n",
    "            ans.append(temp)\n",
    "\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        unionfind = [[t] for t in range(26)]\n",
    "        n = len(s1)\n",
    "        for idx in range(n):\n",
    "\n",
    "            id1 = ord(s1[idx])-ord('a')\n",
    "            id2 = ord(s2[idx])-ord('a')\n",
    "            if unionfind[id1] != unionfind[id2]:\n",
    "                unionfind[id1]+=unionfind[id2]\n",
    "                for k in unionfind[id2]:\n",
    "                    unionfind[k] = unionfind[id1]\n",
    "        \n",
    "\n",
    "        dic = dict()\n",
    "        vis = set()\n",
    "        for x,uf in enumerate(unionfind):\n",
    "            if id(uf) not in vis:\n",
    "                vis.add(id(uf))\n",
    "                for c in uf:\n",
    "                    dic[c+ord('a')]=x+ord('a')\n",
    "\n",
    "\n",
    "        return baseStr.translate(dic)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        n = len(s1)\n",
    "        dic = defaultdict(list)\n",
    "        for dig in 'abcdefghijklmnopqrstuvwxyz':\n",
    "            dic[dig].append(dig)\n",
    "\n",
    "        for i in range(n):\n",
    "            for dig in dic[s1[i]]:\n",
    "                for dig2 in dic[s2[i]]:\n",
    "                    if dig2 not in dic[dig]:\n",
    "                        dic[dig].append(dig2)\n",
    "            for dig in dic[s2[i]]:\n",
    "                for dig2 in dic[s1[i]]:\n",
    "                    if dig2 not in dic[dig]:\n",
    "                        dic[dig].append(dig2)\n",
    "        for dig in 'abcdefghijklmnopqrstuvwxyz':\n",
    "            dic[dig].sort()\n",
    "        baseStr = [c for c in baseStr]\n",
    "        for i in range(len(baseStr)):\n",
    "            baseStr[i] = dic[baseStr[i]][0]\n",
    "        return ''.join(baseStr)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        def find(x):\n",
    "            if p[x] != x:\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "        def union(x, y):\n",
    "            p[find(x)] = p[find(y)] = min(find(x), find(y))\n",
    "        p = list(range(26))\n",
    "        for i, j in zip(s1, s2):\n",
    "            union(ord(i)-97, ord(j)-97)\n",
    "        ans = \"\"\n",
    "        for w in baseStr:\n",
    "            ans += chr(find(ord(w) - 97) + 97)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        unions = [set([i]) for i in range(26)]\n",
    "        for c1, c2 in zip(s1, s2):\n",
    "            i1 = ord(c1)-97\n",
    "            i2 = ord(c2)-97\n",
    "            if len(unions[i1])>len(unions[i2]):\n",
    "                s = unions[i1]\n",
    "                s |= unions[i2]\n",
    "            else:\n",
    "                s = unions[i2]\n",
    "                s |= unions[i1]\n",
    "            for i in s:\n",
    "                unions[i] = s\n",
    "        heads = [min(s) for s in unions]\n",
    "        return \"\".join(map(lambda c: chr(heads[ord(c)-97]+97), baseStr))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import string\n",
    "from collections import defaultdict\n",
    "\n",
    "class UnionFind(object):\n",
    "\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n))\n",
    "    \n",
    "    def find(self, i):\n",
    "        if self.parent[i] != i:\n",
    "            self.parent[i] = self.find(self.parent[i])\n",
    "        return self.parent[i]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        rootx = self.find(x)\n",
    "        rooty = self.find(y)\n",
    "        if rootx == rooty:\n",
    "            return\n",
    "        self.parent[rootx] = rooty\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        index_mapping = {c: i for i, c in enumerate(string.ascii_lowercase)}\n",
    "        union_find = UnionFind(26)\n",
    "        for c1, c2 in zip(s1, s2):\n",
    "            ind1, ind2 = index_mapping[c1], index_mapping[c2]\n",
    "            union_find.union(ind1, ind2)\n",
    "        for i in range(26):\n",
    "            union_find.find(i)\n",
    "        # print(union_find.parent)\n",
    "        similar_chars = defaultdict(list)\n",
    "        for i in range(26):\n",
    "            tmp_char = string.ascii_lowercase[i]\n",
    "            similar_chars[union_find.parent[i]].append(tmp_char)\n",
    "        result = list()\n",
    "        for c in baseStr:\n",
    "            tmp_ind = index_mapping[c]\n",
    "            parent_ind = union_find.parent[tmp_ind]\n",
    "            if parent_ind in similar_chars:\n",
    "                result.append(similar_chars[parent_ind][0])\n",
    "            else:\n",
    "                result.append(c)\n",
    "        return \"\".join(result)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        parent_list = [index for index in range(26)]\n",
    "        answer_list = list(baseStr)\n",
    "        for letter1, letter2 in zip(s1, s2):\n",
    "            parent_letter1 = find(parent_list, ord(letter1) - ord('a'))\n",
    "            parent_letter2 = find(parent_list, ord(letter2) - ord('a'))\n",
    "            if parent_letter1 < parent_letter2:\n",
    "                union(parent_list, parent_letter2, parent_letter1)\n",
    "            elif parent_letter1 > parent_letter2:\n",
    "                union(parent_list, parent_letter1, parent_letter2)\n",
    "        for index in range(len(baseStr)):\n",
    "            answer_list[index] = chr(find(parent_list, ord(baseStr[index]) - ord('a')) + ord('a'))\n",
    "        return ''.join(answer_list)\n",
    "\n",
    "def find(parent_list, index):\n",
    "    if parent_list[index] != index:\n",
    "        parent_list[index] = find(parent_list, parent_list[index])\n",
    "    return parent_list[index]\n",
    "\n",
    "def union(parent_list, index1, index2):\n",
    "    parent_list[find(parent_list, index1)] = find(parent_list, index2)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        fa = list(range(26))\n",
    "        def find(x:int)->int:\n",
    "            if fa[x] == x:\n",
    "                return x \n",
    "            fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        \n",
    "        def unite(x:int,y:int):\n",
    "            a, b = find(x), find(y)\n",
    "            if a != b:\n",
    "                fa[a] = b\n",
    "\n",
    "        for a,b in zip(s1,s2):\n",
    "            unite(ord(a)-ord('a'), ord(b) - ord('a'))\n",
    "\n",
    "        alpha = defaultdict(list)\n",
    "        for i in range(26):\n",
    "            alpha[find(i)].append(chr(i + ord('a')))\n",
    "        \n",
    "        return \"\".join([min(alpha[fa[ord(c)-ord('a')]]) for c in baseStr])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        fa = list(range(26))\n",
    "        def find(x:int)->int:\n",
    "            if fa[x] == x:\n",
    "                return x \n",
    "            fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        \n",
    "        def unite(x:int,y:int):\n",
    "            a, b = find(x), find(y)\n",
    "            if a != b:\n",
    "                fa[a] = b\n",
    "\n",
    "        for a,b in zip(s1,s2):\n",
    "            unite(ord(a)-ord('a'), ord(b) - ord('a'))\n",
    "\n",
    "        alpha = {}\n",
    "        for i in range(26):\n",
    "            if (f:=find(i)) in alpha:\n",
    "                alpha[f] = min(alpha[f],chr(i + ord('a')))\n",
    "            else:\n",
    "                alpha[f] = chr(i + ord('a'))\n",
    "\n",
    "        return \"\".join([alpha[fa[(ord(c)-ord('a'))]] for c in baseStr])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        n = len(s1)\n",
    "        dic = defaultdict(set)\n",
    "        for dig in 'abcdefghijklmnopqrstuvwxyz':\n",
    "            dic[dig].add(dig)\n",
    "        #print(dic)\n",
    "        for i in range(n):\n",
    "            for dig in dic[s1[i]].copy():\n",
    "                for dig2 in dic[s2[i]]:\n",
    "                    if dig2 not in dic[dig]:\n",
    "                        dic[dig].add(dig2)\n",
    "            for dig in dic[s2[i]].copy():\n",
    "                for dig2 in dic[s1[i]]:\n",
    "                    if dig2 not in dic[dig]:\n",
    "                        dic[dig].add(dig2)\n",
    "\n",
    "        baseStr = [c for c in baseStr]\n",
    "        for i in range(len(baseStr)):\n",
    "            baseStr[i] = min(dic[baseStr[i]])\n",
    "        return ''.join(baseStr)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class CDict:\n",
    "    def __init__(self, s1: str, s2: str):\n",
    "        self.s1 = s1\n",
    "        self.s2 = s2\n",
    "\n",
    "        self.d = defaultdict(set)\n",
    "\n",
    "        self.build()\n",
    "\n",
    "    def build(self):\n",
    "        for idx in range(len(self.s1)):\n",
    "            c1 = self.s1[idx]\n",
    "            c2 = self.s2[idx]\n",
    "            \n",
    "            self.d[c1].add(c2)\n",
    "            self.d[c2].add(c1)\n",
    "        \n",
    "    def find(self, c: str):\n",
    "        result = set()\n",
    "        self._find(c, result, set())\n",
    "\n",
    "        result = sorted(result)\n",
    "\n",
    "        if len(result) == 0:\n",
    "            return c\n",
    "        else:\n",
    "            return result[0]\n",
    "    \n",
    "    def _find(self, c: str, result: set, visited: set):\n",
    "        if c in visited:\n",
    "            return\n",
    "        visited.add(c)\n",
    "        result.add(c)\n",
    "        for nc in self.d[c]:\n",
    "            self._find(nc, result, visited)\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        d = CDict(s1, s2)\n",
    "\n",
    "        new_str = \"\"\n",
    "        for c in baseStr:\n",
    "            new_str += d.find(c)\n",
    "\n",
    "\n",
    "        return new_str\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UninoFind:\n",
    "    def __init__(self):\n",
    "        self.parent = {chr(i) : chr(i) for i in range(ord('a'), ord('z') + 1)}\n",
    "        self.rank = {chr(i) : 0 for i in range(ord('a'), ord('z') + 1)}\n",
    "    \n",
    "    def find(self, x):\n",
    "        if x != self.parent[x]:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "        if rootX != rootY:\n",
    "            if self.rank[rootX] > self.rank[rootY]:\n",
    "                self.parent[rootY] = rootX\n",
    "            elif self.rank[rootY] > self.rank[rootX]:\n",
    "                self.parent[rootX] = rootY\n",
    "            else:\n",
    "                self.parent[rootY] = rootX\n",
    "                self.rank[rootX] += 1\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        uf = UninoFind()\n",
    "\n",
    "        for a, b in zip(s1, s2):\n",
    "            uf.union(a, b)\n",
    "        \n",
    "        smallest_equiv = {}\n",
    "        for char in set(s1 + s2):\n",
    "            root = uf.find(char)\n",
    "\n",
    "            if root not in smallest_equiv or char < smallest_equiv[root]:\n",
    "                smallest_equiv[root] = char\n",
    "        \n",
    "        return ''.join(smallest_equiv.get(uf.find(char), char) for char in baseStr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        d = {c: c for c in ascii_lowercase}\n",
    "        def find(c):\n",
    "            if d[c] != c:\n",
    "                d[c] = find(d[c])\n",
    "            return d[c]\n",
    "        for a, b in zip(s1, s2):\n",
    "            if a != b:\n",
    "                a1, b1 = find(a), find(b)\n",
    "                if a1 > b1:\n",
    "                    d[a1] = b1\n",
    "                elif a1 < b1:\n",
    "                    d[b1] = a1\n",
    "        all(map(find, ascii_lowercase))\n",
    "        return ''.join(map(d.get, baseStr))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        #解题思路：\n",
    "        #建立并查集\n",
    "\n",
    "        uf = UnionFind()\n",
    "        for i in range(len(s1)):\n",
    "            uf.add(s1[i])\n",
    "            uf.add(s2[i])\n",
    "            uf.union(s1[i],s2[i])\n",
    "        \n",
    "        res = ''\n",
    "        for i in baseStr:\n",
    "            res += uf.find(i)\n",
    "        return res\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.parent = {}\n",
    "    \n",
    "    def add(self,x):\n",
    "        if x not in self.parent:\n",
    "            self.parent[x] = x\n",
    "    \n",
    "    def find(self,x):\n",
    "        if x not in self.parent:\n",
    "            return x\n",
    "        root = x\n",
    "        while self.parent[root] != root:\n",
    "            root = self.parent[root]\n",
    "\n",
    "        #路径压缩\n",
    "        while root != x:\n",
    "            origin_parent = self.parent[x]\n",
    "            self.parent[x] = root\n",
    "            x = origin_parent\n",
    "        return root\n",
    "    \n",
    "    def union(self,x,y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x < root_y:\n",
    "            self.parent[root_y] = root_x\n",
    "        else:\n",
    "            self.parent[root_x] = root_y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        def c2id(c):\n",
    "            return ord(c) - ord('a')\n",
    "        father = [i for i in range(26)]\n",
    "\n",
    "        def find(u):\n",
    "            if father[u] == u:\n",
    "                return u\n",
    "            father[u] = find(father[u])\n",
    "            return father[u]\n",
    "        def issame(u,v):\n",
    "            return find(u) == find(v)\n",
    "        \n",
    "        def union(u,v):\n",
    "            u = find(u)\n",
    "            v = find(v)\n",
    "            if u == v:\n",
    "                return\n",
    "            father[v] = u\n",
    "\n",
    "        for i in range(len(s1)):\n",
    "            union(c2id(s1[i]),c2id(s2[i]))\n",
    "        res = \"\"\n",
    "        for s in baseStr:\n",
    "            for c in \"abcdefghijklmnopqrstuvwxyz\":\n",
    "                if issame(c2id(c),c2id(s)):\n",
    "                    res += c\n",
    "                    break\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionSet:\n",
    "    def __init__(self):\n",
    "        self.parents = {}\n",
    "    def find(self, x):\n",
    "        if(x != self.parents[x]):\n",
    "            self.parents[x] = self.find(self.parents[x])\n",
    "        return self.parents[x]\n",
    "    def union(self, x, y):\n",
    "        ax = self.find(x)\n",
    "        ay = self.find(y)\n",
    "        if(ax == ay):\n",
    "            return True\n",
    "        if(ax < ay):\n",
    "            ax, ay = ay, ax \n",
    "        self.parents[ax] = ay \n",
    "        return False\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        us = UnionSet()\n",
    "        for i in range(26):\n",
    "            us.parents[chr(i+ord('a'))] = chr(i+ord('a'))\n",
    "        for c1, c2 in zip(s1, s2):\n",
    "            us.union(c1,c2)\n",
    "        result = ''\n",
    "        for c in baseStr:\n",
    "            result += us.find(c)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class unionxy():\n",
    "    def __init__(self,n):\n",
    "        self.root=[i for i in range(n)]\n",
    "    def find(self,x):\n",
    "        if(x!=self.root[x]):\n",
    "            root_x=self.find(self.root[x])\n",
    "            self.root[x]=root_x\n",
    "            return root_x\n",
    "        return x\n",
    "    def union(self,x,y):\n",
    "        root_x=self.find(x)\n",
    "        root_y=self.find(y)\n",
    "        if root_x==root_y:return\n",
    "        if root_x<root_y:\n",
    "            root_x,root_y=root_y,root_x\n",
    "        self.root[root_x]=root_y\n",
    "        return\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        n=len(s1)\n",
    "        uf=unionxy(26)\n",
    "        for i in range(n):\n",
    "            uf.union(ord(s1[i])-ord('a'),ord(s2[i])-ord('a'))\n",
    "        ans=''\n",
    "        for w in baseStr:\n",
    "            ans+=chr(uf.find(ord(w)-ord('a'))+ord('a'))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        parent = [i for i in range(26)]\n",
    "\n",
    "        def find(index):\n",
    "            if parent[index] != index:\n",
    "                parent[index] = find(parent[index])\n",
    "            return parent[index]\n",
    "\n",
    "        def union(index1, index2):\n",
    "            parent[find(index2)] = find(index1)\n",
    "        \n",
    "        for i in range(len(s1)):\n",
    "            # print(ord(s1[i])-ord('a'), ord(s2[i])-ord('a'))\n",
    "            union(ord(s1[i])-ord('a'), ord(s2[i])-ord('a'))\n",
    "        \n",
    "        # print(parent)\n",
    "        \n",
    "        record = collections.defaultdict(list)\n",
    "        for i in range(26):\n",
    "            record[find(i)].append(chr(i+ord('a')))\n",
    "        \n",
    "        for key in record:\n",
    "            record[key].sort()\n",
    "\n",
    "        res = []\n",
    "        for c in baseStr:\n",
    "            index = find(ord(c)-ord('a'))\n",
    "            res.append(record[index][0])\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def init(self):\n",
    "        self.fa = [i for i in range(26)]\n",
    "    def find(self, x):\n",
    "        if self.fa[x] == x:\n",
    "            return x\n",
    "        return self.find(self.fa[x])\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        # 找到连接的点\n",
    "        # 并查集\n",
    "        self.init()\n",
    "        n = len(s1)\n",
    "        for i in range(n):\n",
    "            x, y = ord(s1[i]) - ord('a'), ord(s2[i]) - ord('a')\n",
    "            self.fa[self.find(x)] = self.find(y)\n",
    "        # 找到连接\n",
    "        edges = defaultdict(list)\n",
    "        for x in range(26):\n",
    "            y = self.find(x)\n",
    "            edges[chr(y + ord('a'))].append(chr(x + ord('a')))\n",
    "        equalMap = {x:x for x in baseStr}\n",
    "        for node in edges.keys():\n",
    "            if len(edges[node]) > 1: # 's': ['k', 'r', 's']\n",
    "                sortedEqualNodes = sorted(edges[node])\n",
    "                minC = sortedEqualNodes[0]\n",
    "                for x in sortedEqualNodes[1:]:\n",
    "                    equalMap[x] = minC\n",
    "                    \n",
    "        return \"\".join([equalMap[x] for x in baseStr])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        parent_list = [index for index in range(26)]\n",
    "        answer_list = list(baseStr)\n",
    "        for letter1, letter2 in zip(s1, s2):\n",
    "            parent_letter1 = find(parent_list, ord(letter1) - ord('a'))\n",
    "            parent_letter2 = find(parent_list, ord(letter2) - ord('a'))\n",
    "            if parent_letter1 < parent_letter2:\n",
    "                union(parent_list, parent_letter2, parent_letter1)\n",
    "            elif parent_letter1 > parent_letter2:\n",
    "                union(parent_list, parent_letter1, parent_letter2)\n",
    "        for index in range(len(baseStr)):\n",
    "            answer_list[index] = chr(find(parent_list, ord(baseStr[index]) - ord('a')) + ord('a'))\n",
    "        return ''.join(answer_list)\n",
    "\n",
    "def find(parent_list, index):\n",
    "    if parent_list[index] != index:\n",
    "        parent_list[index] = find(parent_list, parent_list[index])\n",
    "    return parent_list[index]\n",
    "\n",
    "def union(parent_list, index1, index2):\n",
    "    parent_list[index1] = index2\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        root=[i for i in range(26)]\n",
    "        def find(x):\n",
    "            if x==root[x]:\n",
    "                return x\n",
    "            rootx=find(root[x])\n",
    "            root[x]=rootx\n",
    "            return rootx\n",
    "        \n",
    "        def union(x, y):\n",
    "            px=find(x)\n",
    "            py=find(y)\n",
    "            if px==py:\n",
    "                return\n",
    "            if px<py:\n",
    "                px,py=py,px\n",
    "            root[px]=py\n",
    "            return\n",
    "        \n",
    "        n=len(s1)\n",
    "        for i in range(n):\n",
    "            union(ord(s1[i])-ord('a'), ord(s2[i])-ord('a'))\n",
    "        res=''\n",
    "        for ch in baseStr:\n",
    "            res+=chr(find(ord(ch)-ord('a'))+ord('a'))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        parent_list = [index for index in range(26)]\n",
    "        answer_list = list(baseStr)\n",
    "        for letter1, letter2 in zip(s1, s2):\n",
    "            if find(parent_list, ord(letter1) - ord('a')) < find(parent_list, ord(letter2) - ord('a')):\n",
    "                union(parent_list, ord(letter2) - ord('a'), ord(letter1) - ord('a'))\n",
    "            elif find(parent_list, ord(letter1) - ord('a')) > find(parent_list, ord(letter2) - ord('a')):\n",
    "                union(parent_list, ord(letter1) - ord('a'), ord(letter2) - ord('a'))\n",
    "        for index in range(len(baseStr)):\n",
    "            answer_list[index] = chr(find(parent_list, ord(baseStr[index]) - ord('a')) + ord('a'))\n",
    "        return ''.join(answer_list)\n",
    "\n",
    "def find(parent_list, index):\n",
    "    if parent_list[index] != index:\n",
    "        parent_list[index] = find(parent_list, parent_list[index])\n",
    "    return parent_list[index]\n",
    "\n",
    "def union(parent_list, index1, index2):\n",
    "    parent_list[find(parent_list, index1)] = find(parent_list, index2)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.parent = {}\n",
    "        self.rank = defaultdict(lambda: 0)\n",
    "\n",
    "    def find(self, x):\n",
    "        self.parent.setdefault(x, x)\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def union(self, x: int, y: int):\n",
    "        root_x, root_y = self.find(x), self.find(y)\n",
    "        if root_x != root_y:\n",
    "            self.parent[root_x] = root_y\n",
    "\n",
    "    def union_rank(self, x: int, y: int):\n",
    "        x_root, y_root = self.find(x), self.find(y)\n",
    "        if x_root != y_root:\n",
    "            if y_root > x_root:\n",
    "                self.parent[y_root] = x_root\n",
    "            else:\n",
    "                self.parent[x_root] = y_root\n",
    "    \n",
    "    def connected(self, x: int, y: int):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        n = len(s1)\n",
    "        uf = UnionFind()\n",
    "        for a, b in zip(s1, s2):\n",
    "            uf.union_rank(a, b)\n",
    "        ret = ''\n",
    "        for c in baseStr:\n",
    "            ret += uf.find(c)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.parent = {}\n",
    "\n",
    "    def find(self, x):\n",
    "        self.parent.setdefault(x, x)\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def union_rank(self, x: int, y: int):\n",
    "        x_root, y_root = self.find(x), self.find(y)\n",
    "        if x_root != y_root:\n",
    "            if y_root > x_root:\n",
    "                self.parent[y_root] = x_root\n",
    "            else:\n",
    "                self.parent[x_root] = y_root\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        n = len(s1)\n",
    "        uf = UnionFind()\n",
    "        for a, b in zip(s1, s2):\n",
    "            uf.union_rank(a, b)\n",
    "        ret = ''\n",
    "        for c in baseStr:\n",
    "            ret += uf.find(c)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        unionfind = [[t] for t in range(26)]\n",
    "        n = len(s1)\n",
    "        for idx in range(n):\n",
    "\n",
    "            id1 = ord(s1[idx])-ord('a')\n",
    "            id2 = ord(s2[idx])-ord('a')\n",
    "            if unionfind[id1] != unionfind[id2]:\n",
    "                unionfind[id1]+=unionfind[id2]\n",
    "                for k in unionfind[id2]:\n",
    "                    unionfind[k] = unionfind[id1]\n",
    "        \n",
    "\n",
    "        dic = dict()\n",
    "        vis = set()\n",
    "        for x,uf in enumerate(unionfind):\n",
    "            if id(uf) not in vis:\n",
    "                vis.add(id(uf))\n",
    "                for c in uf:\n",
    "                    dic[c+ord('a')]=x+ord('a')\n",
    "\n",
    "\n",
    "        return baseStr.translate(dic)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        def find(x):\n",
    "            if f.setdefault(x, x) != x:\n",
    "                f[x] = find(f[x])\n",
    "            return f[x]\n",
    "        \n",
    "        def union(x, y):\n",
    "            fx, fy = sorted([find(x), find(y)])\n",
    "            f[fy] = fx\n",
    "\n",
    "        f = {}\n",
    "        for a, b in zip(s1, s2):\n",
    "            union(a, b)\n",
    "        return ''.join(find(x) for x in baseStr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def init(self):\n",
    "        self.fa = [i for i in range(26)]\n",
    "    def find(self, x):\n",
    "        if self.fa[x] == x:\n",
    "            return x\n",
    "        return self.find(self.fa[x])\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        # 找到连接的点\n",
    "        # 并查集\n",
    "        self.init()\n",
    "        n = len(s1)\n",
    "        for i in range(n):\n",
    "            x, y = ord(s1[i]) - ord('a'), ord(s2[i]) - ord('a')\n",
    "            # if x > y:\n",
    "            #     x, y = y, x\n",
    "            self.fa[self.find(x)] = self.find(y)\n",
    "        # print(f\"fa:{self.fa}\")\n",
    "        # 找到连接\n",
    "        edges = defaultdict(list)\n",
    "        for x in range(26):\n",
    "            y = self.find(x)\n",
    "            print(f\"x:{chr(x + ord('a'))}, y:{chr(y + ord('a'))}\")\n",
    "            edges[chr(y + ord('a'))].append(chr(x + ord('a')))\n",
    "        # print(f\"edges:{edges}\")\n",
    "        equalMap = {x:x for x in baseStr}\n",
    "        for node in edges.keys():\n",
    "            if len(edges[node]) > 1: # 's': ['k', 'r', 's']\n",
    "                sortedEqualNodes = sorted(edges[node])\n",
    "                minC = sortedEqualNodes[0]\n",
    "                for x in sortedEqualNodes[1:]:\n",
    "                    equalMap[x] = minC\n",
    "        # print(f\"equalMap:{equalMap}\")\n",
    "        return \"\".join([equalMap[x] for x in baseStr])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:\n",
    "        \n",
    "        def union(a, b):\n",
    "            x, y = sorted([find(a), find(b)])\n",
    "            parent[y] = x\n",
    "        \n",
    "        def find(a) -> int:\n",
    "            if parent[a] == a:\n",
    "                return a\n",
    "            parent[a] = find(parent[a])\n",
    "            return parent[a]\n",
    "        \n",
    "        parent = [i for i in range(27)]\n",
    "        n = len(s1)\n",
    "        ps = lambda ch: ord(ch) - ord('a')\n",
    "        for i in range(n):\n",
    "            a, b = ps(s1[i]), ps(s2[i])\n",
    "            if b < a:\n",
    "                a, b = b, a\n",
    "            union(a, b)\n",
    "        res = \"\"\n",
    "        print(parent)\n",
    "        for i in range(len(baseStr)):\n",
    "            ch = ps(baseStr[i])\n",
    "            nch = find(ch)\n",
    "            nchr = chr(nch + ord('a'))\n",
    "            print(baseStr[i], nchr)\n",
    "            res += nchr\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
